package DataStructure.linkList.swordOffer;

import DataStructure.linkList.ListNode;

/**
 * 剑指 Offer 22. 链表中倒数第k个节点
 * 题目简述：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
 */
public class GetKthFromEnd {

    /**
     * 思路：快慢指针：fast指针先走k步，slow再出发。当fast指向null时，则slow指向倒数第k个节点，因为fast领先slow指针k步
     */
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode slow = head, fast = head;
        for(int i = 1;i <= k;i++) {
            fast = fast.next;
        }
        while(fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    /**
     * 思路二：尾递归法
     */
    int t = 0;
    public ListNode getKthFromEnd2(ListNode head, int k) {
        if(head == null) return null;
        ListNode result = getKthFromEnd(head.next, k);
        t++;
        if(t == k) result = head;
        return result;
    }
}
